package datastructures.queue;

import java.lang.reflect.Array;

/**
 * 数组实现队列
 * 循环数组,使用指针指代当前队列的头和尾.
 * 如果头或者尾到数组尾,指针移动到数组头.
 *
 * tip:线程不安全
 *
 * @author hck
 */
public class ArrayQueue<T> {

    /**
     * 由于使用数组实现,不能像链表一样很方便扩容.
     * 初始化队列长度
     */
    private int length;

    /**
     * 队列尾指针
     */
    private int rear = -1;

    /**
     * 队列头指针
     */
    private int front = 0;

    /**
     * 当前队列大小
     */
    private int size;

    /**
     * 存放数据
     */
    private T[] array;

    public ArrayQueue(Class<? extends T> clazz, int length) {
        this.length = length;
        array = (T[]) Array.newInstance(clazz, length);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        if (isEmpty()) {
            return false;
        }
        return size == length;
    }

    /**
     * 出队
     *
     * @return
     */
    public T pop() {
        if (isEmpty()) {
            return null;
        }
        size--;
        T data = array[front];
        array[front] = null;
        if (front == length - 1) {
            //  如果已经指针移动到尾指针
            //  那么出队后指针应该到数组最前面
            front = 0;
        } else {
            front++;
        }
        return data;
    }

    /**
     * 入队
     *
     * @param data
     */
    public void add(T data) {
        if (isFull()) {
            throw new IllegalArgumentException("queue full");
        }
        size++;
        if (rear == length - 1) {
            //  如果已经指针移动到尾指针
            //  那么出队后指针应该到数组最前面
            rear = 0;
        } else {
            rear++;
        }
        array[rear] = data;
    }

    /**
     * 打印当前队列
     */
    public void print() {
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            if (array[i] == null) {
                System.out.print("null");
            } else {
                System.out.print(array[i]);
            }
            if (i != array.length - 1) {
                System.out.print(",");
            }
        }

        System.out.print("]");
        System.out.println();
    }
}
